import java.util.Arrays;

/**
 * @User: vitobo
 * @Date: 2024-06-25
 * @Description: 创建堆
 */


public class MyHeap {
    public int[] elem;

    public int usedSize; //有效的数据个数

    public static final int DEFAULT_SIZE = 10;

    public MyHeap(){
        elem = new int[DEFAULT_SIZE];
    }

    // 初始化数组
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆
     * 时间复杂度 O(N)
     */
    public void createHeap(){
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--){
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整 建大堆
     * parent 每棵子树的根节点
     * len    每棵子树调整的结束位置  不能>len
     *      时间复杂度: O(logN)
     */
     public void shiftDown(int parent, int len){
         int child = 2*parent+1;

         // 1.必须保证有左孩子
         while (child < len){
             // 保证有右孩子
             if(child + 1 < len && elem[child] < elem[child+1]){
                 child++;
             }
             // child下标 一定是左右孩子 最大值的下标
             if(elem[child] > elem[parent]){
                 int tmp = elem[child];
                 elem[child] = elem[parent];
                 elem[parent] = tmp;

                 parent = child;
                 child = parent*2+1;
             }else {
                 break;
             }
         }
     }

     // 入队
    public void offer(int val){
         if(isFull()){
             elem = Arrays.copyOf(this.elem, 2*this.elem.length);
         }
         this.elem[usedSize] = val;
         usedSize++;

         shiftUp(usedSize-1);
    }

    // 删除元素, 向上调整
    public void shiftUp(int child){
         int parent = (child-1)/2;

         while (child > 0){
             if(elem[child] > elem[parent]){
                 int tmp = elem[child];
                 elem[child] = elem[parent];
                 elem[parent] = tmp;

                 child = parent;
                 parent = (child-1)/2;
             }else {
                 break;
             }
         }
    }

    // 出队
    public int pop(){
         if(isEmpty()){
             return -1;
         }

         int tmp = elem[0];
         elem[0] = elem[usedSize-1];
         elem[usedSize-1] = tmp;
         usedSize--;

         // 保证仍然是一棵大根堆
        shiftDown(0, usedSize);
        return tmp;
    }

    // 队头元素
    public int peek(){
         if(isEmpty()){
             return -1;
         }
         return elem[0];
    }

    public boolean isFull(){
         return usedSize == elem.length;
    }

    public boolean isEmpty(){
         return usedSize == 0;
    }

    /**
     * 堆排序
     * 时间复杂度: O(N)+O(N*logN)  约等于 O(NlogN)
     * 空间复杂度 O(1)
     */
    public void heapSort(){
        // 1.建立大根堆
        createHeap();
        // 2.排序
        int end = usedSize-1;
        while (end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;

            shiftDown(0, end);
            end--;
        }
    }
}
